package 蓝桥杯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class day16 {
    public static void main(String[] args) {
       day16 a=new day16();
       /* String str="aabbccbbaa";
        System.out.println( a.partition(str).toString());*/
        /*String str1="123";
        System.out.println( a.restore(str1).toString());*/
       int[] num={1,2,2};
        System.out.println(a.subset5(num).toString());

    }
    List<List<String>> res=new ArrayList<>();
    List<String> path=new ArrayList<>();
    public List<List<String>> partion(String str){
        backing(str,0,new StringBuilder());
        return res;

    }
    public void backing(String str,int start,StringBuilder sb){
        if(start==str.length()){//回溯的途中，符合的都在添加
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=start;i<str.length();i++){
            sb.append(str.charAt(i));
            if(check(sb)){
                path.add(sb.toString());
                backing(str,i+1,new StringBuilder());//创建一个新的
                path.remove(path.size()-1);
            }
        }
    }

    List<List<String>> res1 = new ArrayList<>();
    List<String> cur = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(s, 0, new StringBuilder());
        return res1;
    }
    private void backtracking(String s, int start, StringBuilder sb){
        //因为是起始位置一个一个加的，所以结束时start一定等于s.length,因为进入backtracking时一定末尾也是回文，所以cur是满足条件的
        if (start == s.length()){
            //注意创建一个新的copy
            res1.add(new ArrayList<>(cur));
            return;
        }
        //像前两题一样从前往后搜索，如果发现回文，进入backtracking,起始位置后移一位，循环结束照例移除cur的末位
        for (int i = start; i < s.length(); i++){
            sb.append(s.charAt(i));
            if (check(sb)) {
                cur.add(sb.toString());

                backtracking(s, i + 1, new StringBuilder());
                cur.remove(cur.size() - 1);
            }
        }
    }

    //helper method, 检查是否是回文
    private boolean check(StringBuilder sb){
        for (int i = 0; i < sb.length()/ 2; i++){
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}
        }
        return true;
    }

    List<String> result=new ArrayList<>();


    public List<String> restore(String s){
        //将s的值传入sb里面
        StringBuilder sb=new StringBuilder(s);
        backTracing(sb,0,0);
        return result;
    }
    public void backTracing(StringBuilder sb,int start,int point){
        if(point==3){
            if(isvalid(sb.toString(),start,sb.length()-1)){
                result.add(sb.toString());
            }
            return;
        }
        for(int i=start;i<sb.length();i++){
            if(isvalid(sb.toString(),start,i)){
                //指在sb里面添加一个逗号，并不会覆盖值
                sb.insert(i+1,'.');
                //添加了值
                backTracing(sb,i+2,point+1);
                //删除相关的值
                sb.deleteCharAt(i+1);
            }
            else{
                break;
            }
        }
    }
    public  boolean isvalid(String s,int start,int end){//判断是否符合条件
        if(start>end){
            return false;
        }
        //用于保证不是00开头
        if(s.charAt(start)=='0'&&start!=end){
            return false;
        }
        int num=0;
        for(int i=start;i<=end;i++){
            int digit=s.charAt(i)-'0';
            num=num*10+digit;
            if(num>255){
                return false;
            }
        }
        return true;
    }
    List<List<Integer>> result3=new ArrayList<>();
    LinkedList<Integer> path3=new LinkedList<>();
    public List<List<Integer>> subset(int[] num){
        Arrays.sort(num);
        backing2(num,0);
        return result3;
    }
    private void backing2(int[] num,int start){
        if(start==num.length){
           return;
        }
        for(int i=start;i<num.length;i++){
            path3.add(num[i]);
            result3.add(new ArrayList<>(path3));
            backing2(num,i+1);
            path3.remove(path3.size()-1);
        }
    }


    List<List<Integer>> result4=new ArrayList<>();
    List<Integer> path4=new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> subset2(int[] num){
        Arrays.sort(num);
        backing3(num,0);
        return result4;
    }
    private void backing3(int[] num,int start){
       result4.add(new ArrayList<>(path4));
        for(int i=start;i<num.length;i++){
            //i大于start说明已经存在一个可能的值，则会抛弃
           if(i>start&&num[i]==num[i-1]){
               continue;
           }
            path4.add(num[i]);
            backing3(num,i+1);
            path4.remove(path4.size()-1);
        }

    }
    List<List<Integer>> result5=new ArrayList<>();
    List<Integer> path5=new ArrayList<>();
    public List<List<Integer>> subset5(int[] num){
        Arrays.sort(num);
        backing5(num,0);
        return result5;
    }
    private void backing5(int[] num,int start){
        if(start==num.length) {
           return;
        }
            for(int i=start;i<num.length;i++){
                if(i>start&&num[i]==num[i-1]){
                   continue;
                }
                path5.add(num[i]);
                if(path5.size()>1){
                    result5.add(new ArrayList<>(path5));
                }
                backing5(num,i+1);
                path5.remove(path5.size()-1);
                }
    }
    List<List<Integer>> result6=new ArrayList<>();
    List<Integer> path6=new ArrayList<>();
    public List<List<Integer>> subset6(int[] num){
        backing6(num,0);
        return result6;
    }
    private void backing6(int[] num,int start){
        if(start==num.length){
            return;
        }
        for(int i=start;i<num.length;i++){
            path6.add(num[i]);

        }
    }

}

